<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    960. Minimize Malware Spread
   </h1>
   <p>
    In a network of nodes, each node
    <code>
     i
    </code>
    is directly connected to another node
    <code>
     j
    </code>
    if and only if&nbsp;
    <code>
     graph[i][j] = 1
    </code>
    .
   </p>
   <p>
    Some nodes
    <code>
     initial
    </code>
    are initially infected by malware.&nbsp; Whenever two nodes are directly connected and at least one of those two nodes is infected by malware, both nodes will be infected by malware.&nbsp; This spread of malware will continue until no more nodes can be infected in this manner.
   </p>
   <p>
    Suppose
    <code>
     M(initial)
    </code>
    &nbsp;is the final number of nodes infected with malware in the entire network, after the spread of malware stops.
   </p>
   <p>
    We will&nbsp;remove one node from the initial list.&nbsp; Return the node that if removed, would minimize&nbsp;
    <code>
     M(initial)
    </code>
    .&nbsp; If multiple nodes could be removed to minimize
    <code>
     M(initial)
    </code>
    , return such a node with the smallest index.
   </p>
   <p>
    Note that if a node was removed from the
    <code>
     initial
    </code>
    &nbsp;list of infected nodes, it may still be infected later as a result of the malware spread.
   </p>
   <p>
    &nbsp;
   </p>
   <ol>
   </ol>
   <div>
    <p>
     <strong>
      Example 1:
     </strong>
    </p>
    <pre>
<strong>Input: </strong>graph = <span id="example-input-1-1">[[1,1,0],[1,1,0],[0,0,1]]</span>, initial = <span id="example-input-1-2">[0,1]</span>
<strong>Output: </strong><span id="example-output-1">0</span>
</pre>
    <div>
     <p>
      <strong>
       Example 2:
      </strong>
     </p>
     <pre>
<strong>Input: </strong>graph = <span id="example-input-2-1">[[1,0,0],[0,1,0],[0,0,1]]</span>, initial = <span id="example-input-2-2">[0,2]</span>
<strong>Output: </strong><span id="example-output-2">0</span>
</pre>
     <div>
      <p>
       <strong>
        Example 3:
       </strong>
      </p>
      <pre>
<strong>Input: </strong>graph = <span id="example-input-3-1">[[1,1,1],[1,1,1],[1,1,1]]</span>, initial = <span id="example-input-3-2">[1,2]</span>
<strong>Output: </strong><span id="example-output-3">1</span>
</pre>
      <p>
       &nbsp;
      </p>
      <p>
       <strong>
        Note:
       </strong>
      </p>
      <ol>
       <li>
        <code>
         1 &lt; graph.length = graph[0].length &lt;= 300
        </code>
       </li>
       <li>
        <code>
         0 &lt;= graph[i][j] == graph[j][i] &lt;= 1
        </code>
       </li>
       <li>
        <code>
         graph[i][i] = 1
        </code>
       </li>
       <li>
        <code>
         1 &lt;= initial.length &lt; graph.length
        </code>
       </li>
       <li>
        <code>
         0 &lt;= initial[i] &lt; graph.length
        </code>
       </li>
      </ol>
     </div>
    </div>
   </div>
  </div>
  <div>
   <h1 class="question_title">
    960. 尽量减少恶意软件的传播
   </h1>
   <p>
    在节点网络中，只有当
    <code>
     graph[i][j] = 1
    </code>
    &nbsp;时，每个节点&nbsp;
    <code>
     i
    </code>
    &nbsp;能够直接连接到另一个节点
    <code>
     j
    </code>
    。
   </p>
   <p>
    一些节点&nbsp;
    <code>
     initial
    </code>
    &nbsp;最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
   </p>
   <p>
    假设
    <code>
     M(initial)
    </code>
    是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
   </p>
   <p>
    我们可以从初始列表中删除一个节点。如果移除这一节点将最小化
    <code>
     M(initial)
    </code>
    ，&nbsp;则返回该节点。如果有多个节点满足条件，就返回索引最小的节点。
   </p>
   <p>
    请注意，如果某个节点已从受感染节点的列表
    <code>
     initial
    </code>
    中删除，它以后可能仍然因恶意软件传播而受到感染。
   </p>
   <p>
    &nbsp;
   </p>
   <ol>
   </ol>
   <p>
    <strong>
     示例 1：
    </strong>
   </p>
   <pre><strong>输入：</strong>graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
<strong>输出：</strong>0
</pre>
   <p>
    <strong>
     示例 2：
    </strong>
   </p>
   <pre><strong>输入：</strong>graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
<strong>输出：</strong>0
</pre>
   <p>
    <strong>
     示例 3：
    </strong>
   </p>
   <pre><strong>输入：</strong>graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
<strong>输出：</strong>1
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     <code>
      1 &lt; graph.length = graph[0].length &lt;= 300
     </code>
    </li>
    <li>
     <code>
      0 &lt;= graph[i][j] == graph[j][i] &lt;= 1
     </code>
    </li>
    <li>
     <code>
      graph[i][i] = 1
     </code>
    </li>
    <li>
     <code>
      1 &lt;= initial.length &lt; graph.length
     </code>
    </li>
    <li>
     <code>
      0 &lt;= initial[i] &lt; graph.length
     </code>
    </li>
   </ol>
  </div>
 </body>
</html>